package leetcode.code1255;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {

	int[] score;
	String[] words;
	int len;

	public int maxScoreWords(String[] words, char[] letters, int[] score) {
		this.score = score;
		this.words = words;
		this.len = words.length;
		int[] nums = new int[26];
		for (char c : letters) {
			nums[c - 'a']++;
		}
		int len = words.length;
		int[] scores = new int[len];
		Integer[] hash = new Integer[1 << len];
		// 当前决策位置，还能选的字符集合，分数，hash，hashkey
		return this.score(0, nums, 0, hash, 0);
	}

	private int score(int index, int[] nums, int sum, Integer[] hash, int key) {
		if (index == len) {
			hash[key] = sum;
			return sum;
		}
		if (hash[key] != null) {
			return hash[key];
		}
		int ans = this.score(index + 1, nums, sum, hash, key);

		String cur = this.words[index];
		int curSum = 0;
		int[] nextNums = Arrays.copyOf(nums, 26);
		boolean select = true;
		for (char c : cur.toCharArray()) {
			int idx = c - 'a';
			curSum += this.score[idx];
			nextNums[idx]--;
			if (nextNums[idx] < 0) {
				select = false;
				break;
			}
		}
		if (select) {
			ans = Math.max(ans, this.score(index + 1, nextNums, sum + curSum, hash, key | (1 << index)));
		}
		hash[key] = ans;
		return ans;
	}

	@Override
	public void debug4() {
//		H.compare(23, this.maxScoreWords(H.str2array2(null), null, score))

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
